﻿using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;

namespace SampleCode.VirtualFS
{
    /// <summary>
    /// An internal file table
    /// </summary>
    [Serializable]
    internal class FsFileTable
    {
        /// <summary>
        /// Path character replacement table entry
        /// </summary>
        private struct CharReplacementEntry
        {
            public char InternalChar;
            public char ExternalChar;
        }

        /// <summary>
        /// Path character replacement table. InternalChars are considered invalid in external path
        /// </summary>
        private static readonly CharReplacementEntry[] CharReplacementTable = new[]
        {
            new CharReplacementEntry{ InternalChar = '!', ExternalChar = '\\' },
            new CharReplacementEntry{ InternalChar = ':', ExternalChar = ' '  }
        };

        /// <summary>
        /// As the folder tree is stored as a sorted list, we need to use this symbol as a separator (it's considered less than any other char when comparing strings)
        /// </summary>
        public const char InternalPathSeparator = '!';
        public const string InternalPathSeparatorString = "!";

        /// <summary>
        /// Buffer size for block copy operations
        /// </summary>
        public const int BlockCopyBufferSize = 0x2000;

        /// <summary>
        /// The space to reserve for a file growing. The initial gap between two neighbour files.
        /// </summary>
        public const int ReservedSpaceForGrowing = 0x400;

        /// <summary>
        /// List of folders
        /// </summary>
        public SortedList<string, FsInternalFolderInfo> FolderList = new SortedList<string, FsInternalFolderInfo>();

        /// <summary>
        /// Linked list of all files, for fast searching for free space
        /// </summary>
        public LinkedList<FsInternalFileInfo> FileList = new LinkedList<FsInternalFileInfo>();

        /// <summary>
        /// The offset of file data space
        /// </summary>
        public int DataStartOffset = 0x20000;

        /// <summary>
        /// ctor
        /// </summary>
        internal FsFileTable()
        {
            // adding root folder
            FolderList.Add(InternalPathSeparatorString, new FsInternalFolderInfo());
        }

        /// <summary>
        /// Creates a folder. If parent folders do not exist, they're recursively created
        /// </summary>
        /// <param name="folderName">UNC full path for the newly created folder</param>
        /// <param name="failIfExists">Raise an exception if a folder already exists?</param>
        /// <returns>Newly created FsInternalFolderInfo object</returns>
        public FsInternalFolderInfo CreateFolder(string folderName, bool failIfExists)
        {
            var pathParts = SplitPathAndCheck(ref folderName);

            // checking parent folders
            string curFolder = InternalPathSeparatorString;
            for(int i = 2; i < pathParts.Length-1; i++)
            {
                curFolder = curFolder + InternalPathSeparatorString + pathParts[i];
                if(!FolderList.ContainsKey(curFolder))
                    FolderList.Add(curFolder, new FsInternalFolderInfo());
            }

            if 
            (
                (!failIfExists)
                &&
                (FolderList.ContainsKey(folderName))
            )
                return FolderList[folderName];

            var folderInfo = new FsInternalFolderInfo();
            FolderList.Add(folderName, folderInfo);

            return folderInfo;
        }

        /// <summary>
        /// Removes a folder
        /// </summary>
        /// <param name="folderName">UNC full path for the folder to remove</param>
        public void RemoveFolder(string folderName)
        {
            SplitPathAndCheck(ref folderName);

            // checking if folder exists
            int startIndex = FolderList.IndexOfKey(folderName);
            if (startIndex < 0)
                return;

            if(startIndex == 0)
                throw new ArgumentException("Root folder cannot be removed");

            // iterating through the sorted list of folders till the parent path is still in place
            // first to check if any files are open
            int index = startIndex;
            while
            (
                (index < FolderList.Count)
                &&
                (IsFolderOrSubfolder(folderName, FolderList.Keys[index]))
            )
            {
                if (FolderList.Values[index].Files.Where(fi => fi.Value.IsOpen).Count() > 0)
                    throw new UnauthorizedAccessException("A file is open in the folder or it's subfolder");

                index++;
            }

            // iterating through the sorted list of folders till the parent path is still in place
            index = startIndex;
            while
            (
                (index < FolderList.Count)
                &&
                (IsFolderOrSubfolder(folderName, FolderList.Keys[index]))
            )
            {
                // removing files
                foreach (var fileInfo in FolderList.Values[index].Files)
                {
                    FileList.Remove(fileInfo.Value);
                }
                
                FolderList.RemoveAt(index);
            }
        }

        /// <summary>
        /// Renames a folder
        /// </summary>
        /// <param name="oldName">UNC full path for the folder to rename</param>
        /// <param name="newName">New folder name</param>
        public void RenameFolder(string oldName, string newName)
        {
            if (oldName == newName)
                return;

            SplitPathAndCheck(ref oldName);
            var newPathParts = SplitPathAndCheck(ref newName);

            // checking if folder exists
            int startIndex = FolderList.IndexOfKey(oldName);
            if (startIndex < 0)
                throw new ArgumentException("The folder doesn't exist");

            if (FolderList.ContainsKey(newName))
                throw new ArgumentException("A folder with the same name already exist");

            // checking if parent folder exists
            string parentFolderName = newName.Substring(0, newName.Length - newPathParts.Last().Length - 1);
            if (!FolderList.ContainsKey(parentFolderName))
                throw new ArgumentException("The parent folder to move to doesn't exist");

            // iterating through the sorted list of folders till the parent path is still in place
            // first to check if any files are open
            var listToMove = new List<string>();
            int index = startIndex;
            while
            (
                (index < FolderList.Count)
                &&
                (IsFolderOrSubfolder(oldName, FolderList.Keys[index]))
            )
            {
                if (FolderList.Values[index].Files.Where(fi => fi.Value.IsOpen).Count() > 0)
                    throw new UnauthorizedAccessException("A file is open in the folder or it's subfolder");

                listToMove.Add(FolderList.Keys[index]);

                index++;
            }

            // removing and adding back the folder and all subfolders
            foreach (var oldFolderName in listToMove)
            {
                string newFolderName = newName + oldFolderName.Substring(oldName.Length);

                var folderInfo = FolderList[oldFolderName];
                FolderList.Remove(oldFolderName);
                FolderList.Add(newFolderName, folderInfo);
            }
        }

        /// <summary>
        /// Creates a file
        /// </summary>
        /// <param name="fullName">UNC full path for the new file</param>
        /// <returns>FsInternalFileInfo object with file information</returns>
        public FsInternalFileInfo CreateFile(string fullName)
        {
            string folderName, fileName;
            SplitToPathAndFileName(ref fullName, out folderName, out fileName);

            // getting a folder
            var folderInfo = FolderList[folderName];

            var fileInfo = new FsInternalFileInfo();

            // checking if the file already exists
            if(folderInfo.Files.ContainsKey(fileName))
                throw new ArgumentException("The file already exists");

            // searching for a gap in files

            int curEndOffset = 0;
            var curNode = FileList.First;
            while(curNode != null)
            {
                if (curEndOffset + ReservedSpaceForGrowing < curNode.Value.Start)
                    break;

                curEndOffset = curNode.Value.End;
                curNode = curNode.Next;
            }

            if (curNode == null)
            {
                // if no gap found - then adding to the end
                curNode = FileList.AddLast(fileInfo);
            }
            else
            {
                // if a gap found - inserting a file 
                curNode = FileList.AddBefore(curNode, fileInfo);
            }

            if (curNode.Previous != null)
            {
                // file start offset
                fileInfo.Start = curNode.Previous.Value.End + ReservedSpaceForGrowing;
            }

            folderInfo.Files.Add(fileName, fileInfo);

            return fileInfo;
        }

        /// <summary>
        /// Gets file metadata
        /// </summary>
        /// <param name="fullName">UNC full path to the file</param>
        /// <returns>FsInternalFileInfo</returns>
        public FsInternalFileInfo GetFile(string fullName)
        {
            string folderName, fileName;
            SplitToPathAndFileName(ref fullName, out folderName, out fileName);

            // getting a folder
            var folderInfo = FolderList[folderName];
            return folderInfo.Files[fileName];
        }

        /// <summary>
        /// Removes a file
        /// </summary>
        /// <param name="fullName">UNC full path to the file</param>
        public void RemoveFile(string fullName)
        {
            string folderName, fileName;
            SplitToPathAndFileName(ref fullName, out folderName, out fileName);

            // getting file metadata from folder's list
            var folderInfo = FolderList[folderName];
            FsInternalFileInfo fileInfo;
            if(!folderInfo.Files.TryGetValue(fileName, out fileInfo))
                return;

            if(fileInfo.IsOpen)
                throw new UnauthorizedAccessException("The file is open");

            // removing file
            FileList.Remove(fileInfo);
            folderInfo.Files.Remove(fileName);
        }

        /// <summary>
        /// Renames/moves a file
        /// </summary>
        /// <param name="oldName">UNC full path to the file to rename</param>
        /// <param name="newName">New file name</param>
        public void RenameFile(string oldName, string newName)
        {
            string oldFolderName, oldFileName, newFolderName, newFileName;
            SplitToPathAndFileName(ref oldName, out oldFolderName, out oldFileName);
            SplitToPathAndFileName(ref newName, out newFolderName, out newFileName);

            if (oldName == newName)
                return;

            // getting folders
            var oldFolderInfo = FolderList[oldFolderName];
            var newFolderInfo = FolderList[newFolderName];

            if(newFolderInfo.Files.ContainsKey(newFileName))
                throw new ArgumentException("A file with the same name already exists in destination folder");

            // getting a file
            var fileInfo = oldFolderInfo.Files[oldFileName];

            if(fileInfo.IsOpen)
                throw new UnauthorizedAccessException("The file is open");

            // moving file
            oldFolderInfo.Files.Remove(oldFileName);
            newFolderInfo.Files.Add(newFileName, fileInfo);
        }

        /// <summary>
        /// Enumerates subfolders
        /// </summary>
        /// <param name="folderName">Parent folder name</param>
        /// <param name="recursive">Return all grandchildren?</param>
        /// <returns>IEnumerable of FsFolderInfo</returns>
        public IEnumerable<FsFolderInfo> GetSubFolders(string folderName, bool recursive)
        {
            SplitPathAndCheck(ref folderName);

            // Checking if folder exists
            int index = FolderList.IndexOfKey(folderName);
            if (index < 0)
                throw new ArgumentException("The folder doesn't exist");

            // skipping the folder itself
            index++;

            // iterating through the sorted list of folders till the parent path is still in place
            while 
            (
                (index < FolderList.Count)
                &&
                (IsFolderOrSubfolder(folderName, FolderList.Keys[index]))
            )
            {
                if
                (
                    (recursive)
                    ||
                    (IsDirectChildFolder(folderName, FolderList.Keys[index]))
                )
                {
                    yield return
                        new FsFolderInfo
                        (
                            MakeExternalPath(FolderList.Keys[index].Substring(folderName.Length + 1)),
                            MakeExternalPath(FolderList.Keys[index])
                        );
                }

                index++;
            }
        }

        /// <summary>
        /// Returns files from a folder
        /// </summary>
        /// <param name="folderName">Folder name</param>
        /// <returns>IEnumerable of FsFileInfo</returns>
        public IEnumerable<FsFileInfo> GetFiles(string folderName)
        {
            SplitPathAndCheck(ref folderName);

            var folderInfo = FolderList[folderName];
            return 
                from f in folderInfo.Files select 
                    new FsFileInfo
                    (
                        MakeExternalPath(f.Key), 
                        MakeExternalPath(folderName + InternalPathSeparatorString + f.Key), 
                        f.Value
                    );
        }

        /// <summary>
        /// Finds files matching a pattern in a folder and it's subfolders
        /// </summary>
        /// <param name="folderName">Folder name</param>
        /// <param name="pattern">A pattern to match. Can contain * and ? metacharacters</param>
        /// <returns>IEnumerable of FsFolderInfo</returns>
        public IEnumerable<FsFileInfo> FindFiles(string folderName, string pattern)
        {
            SplitPathAndCheck(ref folderName);

            foreach (var crEntry in CharReplacementTable)
            {
                if (pattern.Contains(crEntry.InternalChar))
                    throw new ArgumentException("The pattern contains an invalid character: " + crEntry.InternalChar);

                pattern = pattern.Replace(crEntry.ExternalChar, crEntry.InternalChar);
            }

            // translating metacharacters to regex quantifiers
            pattern = pattern.Replace("*", ".*");
            pattern = pattern.Replace("?", ".");

            // Checking if folder exists
            int index = FolderList.IndexOfKey(folderName);
            if (index < 0)
                throw new ArgumentException("The folder doesn't exist");

            // iterating through the sorted list of folders till the parent path is still in place
            while
            (
                (index < FolderList.Count)
                &&
                (IsFolderOrSubfolder(folderName, FolderList.Keys[index]))
            )
            {
                foreach (var fileInfo in FolderList.Values[index].Files)
                {
                    if (Regex.IsMatch(fileInfo.Key, pattern))
                    {
                        yield return
                            new FsFileInfo
                            (
                                MakeExternalPath(fileInfo.Key),
                                MakeExternalPath(FolderList.Keys[index] + InternalPathSeparatorString + fileInfo.Key),
                                fileInfo.Value
                            );
                    }
                }

                index++;
            }
        }

        // private methods

        /// <summary>
        /// A routine for restoring external path
        /// </summary>
        /// <param name="internalPath">internal</param>
        /// <returns></returns>
        private static string MakeExternalPath(string internalPath)
        {
            var result = new StringBuilder(internalPath);

            foreach(var crEntry in CharReplacementTable)
            {
                result.Replace(crEntry.InternalChar, crEntry.ExternalChar);
            }

            return result.ToString();
        }

        /// <summary>
        /// A routine for checking path correctness
        /// </summary>
        /// <param name="path">UNC full path</param>
        /// <returns>string[]</returns>
        private static string[] SplitPathAndCheck(ref string path)
        {
            var pathBuilder = new StringBuilder(path);
            foreach (var crEntry in CharReplacementTable)
            {
                if (path.Contains(crEntry.InternalChar))
                    throw new ArgumentException("The path contains an invalid character: " + crEntry.InternalChar);

                pathBuilder.Replace(crEntry.ExternalChar, crEntry.InternalChar);
            }
            path = pathBuilder.ToString();

            var pathParts = path.Split(InternalPathSeparator);

            // the first two parts should be empty - because of UNC format)
            if
            (
                (pathParts.Length < 2)
                ||
                (pathParts[0].Length > 0)
                ||
                (pathParts[1].Length > 0)
            )
                throw new ArgumentException("The path has invalid format");

            // there should be no more empty parts
            if (pathParts.Skip(2).Any(p => p.Length <= 0))
            {
                throw new ArgumentException("The path has invalid format");
            }

            return pathParts;
        }

        /// <summary>
        /// Checks a file full name and breaks it into path and filename
        /// </summary>
        /// <param name="fullName">UNC full file name</param>
        /// <param name="path">Returned path</param>
        /// <param name="fileName">Returned file name</param>
        private static void SplitToPathAndFileName(ref string fullName, out string path, out string fileName)
        {
            var pathParts = SplitPathAndCheck(ref fullName);
            path = fullName.Substring(0, fullName.Length - pathParts.Last().Length - 1);
            fileName = pathParts.Last();
        }

        /// <summary>
        /// A routine that checks if a folder is the same or a child of another
        /// </summary>
        /// <param name="parentName"></param>
        /// <param name="childName"></param>
        /// <returns>bool</returns>
        private static bool IsFolderOrSubfolder(string parentName, string childName)
        {
            if (parentName == childName)
                return true;

            if (childName.Length <= parentName.Length)
                return false;

            // if this is another folder just ending with the same letters
            return childName[parentName.Length] == InternalPathSeparator;
        }

        /// <summary>
        /// A routine that checks if a folder is a direct child of another folder
        /// </summary>
        /// <param name="parentName"></param>
        /// <param name="childName"></param>
        /// <returns></returns>
        private static bool IsDirectChildFolder(string parentName, string childName)
        {
            if (childName.Length <= parentName.Length)
                return false;

            if (childName[parentName.Length] != InternalPathSeparator)
                return false;

            return !childName.Substring(parentName.Length + 1).Contains(InternalPathSeparator);
        }

#if DEBUG

        public void TraceFileList()
        {
            Trace.WriteLine("# File list #");

            LinkedListNode<FsInternalFileInfo> fileNode = FileList.First;
            while(fileNode != null)
            {
                Trace.WriteLine( GetFileName(fileNode.Value) + "(" + fileNode.Value + ")" );

                if(fileNode.Next != null)
                    Trace.WriteLine("-" + (fileNode.Next.Value.Start - fileNode.Value.End) + "-" );

                fileNode = fileNode.Next;
            }
        }

        private string GetFileName(FsInternalFileInfo fileInfo)
        {
            foreach (var folderNode in FolderList)
            {
                foreach (var fileNode in folderNode.Value.Files)
                {
                    if (fileNode.Value == fileInfo)
                        return folderNode.Key + InternalPathSeparatorString + fileNode.Key;
                }
            }
            return "";
        }

#endif
    }
}
